package com.wmx.datastructuresandalgorithms.sortalgorithm.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**********************************
 * @author wmx
 * @date 2019/9/2 9:08
 * @description:
 * @version 1.0
 ************************************/
public class BinarySearch {
    public static void main(String[] args) {
     // int [] arr = {1,100,100,100,1000,300};
      int [] arr = new int[100];
        for (int i = 0; i <100 ; i++) {

            arr[i] = i;

        }
      List<Integer> list =  binarySearch(arr,0,arr.length-1,1);

        System.out.println(list);

    }

    /**
     * @param arr  查询数组
     * @param let  数组的起始位置
     * @param right 数组的终点位置
     * @param value 待查询的值
     */
    public static List<Integer> binarySearch(int [] arr, int let , int right, int value){
        System.out.println("查询了次数");
         int mid = (let + right) / 2;
         if(let > right){  //处理查询不到的情况
             return  new ArrayList<Integer>();
         }
         if (arr[mid] > value){
            return binarySearch(arr,let,mid-1,value);
         }else if (arr[mid] < value){
            return binarySearch(arr,mid+1,right,value);
         }else {  //处理数组中有多个值的情况
             List<Integer> list = new ArrayList<>();
             //向左循环，获取匹配的值。
             int temp = mid -1 ;
             while (true)  {
                 if(temp < 0 || arr[temp] != value){
                     break;
                 }
                 list.add(temp);
                 temp -- ;
             }

             list.add(mid);
            temp = mid + 1 ;
            while (true){
                if(temp > arr.length-1 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
         }
    }
}
